home *** CD-ROM | disk | FTP | other *** search
/ PC World 2001 March / PCWorld_2001-03_cd.bin / Software / TemaCD / classbuild / ClassBuilder 2.2 PR405 Setup.exe / {app} / Include / CB_AvlTree.h next >
Encoding:
C/C++ Source or Header  |  2000-12-29  |  39.2 KB  |  1,191 lines
  1. #ifndef CB_AVLTREE_H
  2. #define CB_AVLTREE_H
  3.  
  4. #include <assert.h>
  5.  
  6. #include "CB_IteratorMulti.h"
  7.  
  8. // defines for include files
  9. #define RELATION_TEMPLATE_AVLTREE_ACTIVE(member, ClassFrom, NameFrom, ClassTo, NameTo) \
  10. private:\
  11.     ClassTo* _top##NameTo;\
  12.     int _count##NameTo;\
  13. \
  14. public:\
  15.     void Add##NameTo(ClassTo* item)\
  16.     {\
  17.         METHOD_AVLTREE_ADD(member, ClassFrom, NameFrom, ClassTo, NameTo) \
  18.     }\
  19.     void Remove##NameTo(ClassTo* item)\
  20.     {\
  21.         METHOD_AVLTREE_REMOVE(ClassFrom, NameFrom, ClassTo, NameTo) \
  22.     }\
  23.     void RemoveAll##NameTo()\
  24.     {\
  25.         METHOD_AVLTREE_REMOVEALL(ClassFrom, NameFrom, ClassTo, NameTo) \
  26.     }\
  27.     void DeleteAll##NameTo()\
  28.     {\
  29.         METHOD_AVLTREE_DELETEALL(ClassFrom, NameFrom, ClassTo, NameTo) \
  30.     }\
  31.     void Replace##NameTo(ClassTo* item, ClassTo* newItem)\
  32.     {\
  33.         METHOD_AVLTREE_REPLACE(member, ClassFrom, NameFrom, ClassTo, NameTo) \
  34.     }\
  35.     ClassTo* GetFirst##NameTo() const\
  36.     {\
  37.         METHOD_AVLTREE_GETFIRST(ClassFrom, NameFrom, ClassTo, NameTo) \
  38.     }\
  39.     ClassTo* GetLast##NameTo() const\
  40.     {\
  41.         METHOD_AVLTREE_GETLAST(ClassFrom, NameFrom, ClassTo, NameTo) \
  42.     }\
  43.     ClassTo* GetNext##NameTo(ClassTo* pos) const\
  44.     {\
  45.         METHOD_AVLTREE_GETNEXT(ClassFrom, NameFrom, ClassTo, NameTo) \
  46.     }\
  47.     ClassTo* GetPrev##NameTo(ClassTo* pos) const\
  48.     {\
  49.         METHOD_AVLTREE_GETPREV(ClassFrom, NameFrom, ClassTo, NameTo) \
  50.     }\
  51.     int Get##NameTo##Count() const\
  52.     {\
  53.         METHOD_AVLTREE_GETCOUNT(ClassFrom, NameFrom, ClassTo, NameTo) \
  54.     }\
  55.     ITERATOR_TEMPLATE_MULTI_ACTIVE(ClassFrom, NameFrom, ClassTo, NameTo)
  56.  
  57. #define RELATION_TEMPLATE_NOFILTER_AVLTREE_ACTIVE(member, ClassFrom, NameFrom, ClassTo, NameTo) \
  58. private:\
  59.     ClassTo* _top##NameTo;\
  60.     int _count##NameTo;\
  61. \
  62. public:\
  63.     void Add##NameTo(ClassTo* item)\
  64.     {\
  65.         METHOD_AVLTREE_ADD(member, ClassFrom, NameFrom, ClassTo, NameTo) \
  66.     }\
  67.     void Remove##NameTo(ClassTo* item)\
  68.     {\
  69.         METHOD_AVLTREE_REMOVE(ClassFrom, NameFrom, ClassTo, NameTo) \
  70.     }\
  71.     void RemoveAll##NameTo()\
  72.     {\
  73.         METHOD_AVLTREE_REMOVEALL(ClassFrom, NameFrom, ClassTo, NameTo) \
  74.     }\
  75.     void DeleteAll##NameTo()\
  76.     {\
  77.         METHOD_AVLTREE_DELETEALL(ClassFrom, NameFrom, ClassTo, NameTo) \
  78.     }\
  79.     void Replace##NameTo(ClassTo* item, ClassTo* newItem)\
  80.     {\
  81.         METHOD_AVLTREE_REPLACE(member, ClassFrom, NameFrom, ClassTo, NameTo) \
  82.     }\
  83.     ClassTo* GetFirst##NameTo() const\
  84.     {\
  85.         METHOD_AVLTREE_GETFIRST(ClassFrom, NameFrom, ClassTo, NameTo) \
  86.     }\
  87.     ClassTo* GetLast##NameTo() const\
  88.     {\
  89.         METHOD_AVLTREE_GETLAST(ClassFrom, NameFrom, ClassTo, NameTo) \
  90.     }\
  91.     ClassTo* GetNext##NameTo(ClassTo* pos) const\
  92.     {\
  93.         METHOD_AVLTREE_GETNEXT(ClassFrom, NameFrom, ClassTo, NameTo) \
  94.     }\
  95.     ClassTo* GetPrev##NameTo(ClassTo* pos) const\
  96.     {\
  97.         METHOD_AVLTREE_GETPREV(ClassFrom, NameFrom, ClassTo, NameTo) \
  98.     }\
  99.     int Get##NameTo##Count() const\
  100.     {\
  101.         METHOD_AVLTREE_GETCOUNT(ClassFrom, NameFrom, ClassTo, NameTo) \
  102.     }\
  103.     ITERATOR_TEMPLATE_NOFILTER_MULTI_ACTIVE(ClassFrom, NameFrom, ClassTo, NameTo)
  104.  
  105. #define RELATION_AVLTREE_ACTIVE(ClassFrom, NameFrom, ClassTo, NameTo) \
  106. private:\
  107.     ClassTo* _top##NameTo;\
  108.     int _count##NameTo;\
  109. \
  110. public:\
  111.     void Add##NameTo(ClassTo* item);\
  112.     void Remove##NameTo(ClassTo* item);\
  113.     void RemoveAll##NameTo();\
  114.     void DeleteAll##NameTo();\
  115.     void Replace##NameTo(ClassTo* item, ClassTo* newItem);\
  116.     ClassTo* GetFirst##NameTo() const;\
  117.     ClassTo* GetLast##NameTo() const;\
  118.     ClassTo* GetNext##NameTo(ClassTo* pos) const;\
  119.     ClassTo* GetPrev##NameTo(ClassTo* pos) const;\
  120.     int Get##NameTo##Count() const;\
  121.     ITERATOR_MULTI_ACTIVE(ClassFrom, NameFrom, ClassTo, NameTo)
  122.  
  123. #define RELATION_NOFILTER_AVLTREE_ACTIVE(ClassFrom, NameFrom, ClassTo, NameTo) \
  124. private:\
  125.     ClassTo* _top##NameTo;\
  126.     int _count##NameTo;\
  127. \
  128. public:\
  129.     void Add##NameTo(ClassTo* item);\
  130.     void Remove##NameTo(ClassTo* item);\
  131.     void RemoveAll##NameTo();\
  132.     void DeleteAll##NameTo();\
  133.     void Replace##NameTo(ClassTo* item, ClassTo* newItem);\
  134.     ClassTo* GetFirst##NameTo() const;\
  135.     ClassTo* GetLast##NameTo() const;\
  136.     ClassTo* GetNext##NameTo(ClassTo* pos) const;\
  137.     ClassTo* GetPrev##NameTo(ClassTo* pos) const;\
  138.     int Get##NameTo##Count() const;\
  139.     ITERATOR_NOFILTER_MULTI_ACTIVE(ClassFrom, NameFrom, ClassTo, NameTo)
  140.  
  141. #define RELATION_AVLTREE_PASSIVE(ClassFrom, NameFrom, ClassTo, NameTo) \
  142. public:\
  143.     ClassFrom* _ref##NameFrom;\
  144.     ClassTo* _parent##NameFrom;\
  145.     ClassTo* _left##NameFrom;\
  146.     ClassTo* _right##NameFrom;\
  147.     int _bal##NameFrom;\
  148. \
  149. public:\
  150.     ClassFrom* Get##NameFrom() const { return _ref##NameFrom; };
  151.  
  152. // defines implementation
  153. #define INIT_AVLTREE_ACTIVE(ClassFrom, NameFrom, ClassTo, NameTo) \
  154.     _top##NameTo = (ClassTo*)0;\
  155.     _count##NameTo = 0;
  156.  
  157. #define EXIT_AVLTREE_ACTIVE(ClassFrom, NameFrom, ClassTo, NameTo) \
  158.     while (_top##NameTo)\
  159.     {\
  160.         Remove##NameTo(_top##NameTo);\
  161.     }
  162.  
  163. #define REPLACE_AVLTREE_ACTIVE(ClassFrom, NameFrom, ClassTo, NameTo) \
  164.     _top##NameTo = pOld->_top##NameTo;\
  165.     _count##NameTo = pOld->_count##NameTo;\
  166.     pOld->_top##NameTo = (ClassTo*)0;\
  167.     { for (ClassTo* item = GetFirst##NameTo(); item; item = GetNext##NameTo(item))\
  168.           item->_ref##NameFrom = this; }
  169.  
  170. #define INIT_AVLTREE_PASSIVE(ClassFrom, NameFrom, ClassTo, NameTo) \
  171.     _ref##NameFrom = (ClassFrom*)0;\
  172.     _parent##NameFrom = (ClassTo*)0;\
  173.     _left##NameFrom = (ClassTo*)0;\
  174.     _right##NameFrom = (ClassTo*)0;\
  175.     _bal##NameFrom = 0;
  176.  
  177. #define EXIT_AVLTREE_PASSIVE(ClassFrom, NameFrom, ClassTo, NameTo) \
  178.     if (_ref##NameFrom)\
  179.         _ref##NameFrom->Remove##NameTo(this);
  180.  
  181. #define REPLACE_AVLTREE_PASSIVE(ClassFrom, NameFrom, ClassTo, NameTo) \
  182.     _ref##NameFrom = (ClassFrom*)0;\
  183.     _parent##NameFrom = (ClassTo*)0;\
  184.     _left##NameFrom = (ClassTo*)0;\
  185.     _right##NameFrom = (ClassTo*)0;\
  186.     _bal##NameFrom = 0;\
  187.     if (pOld->_ref##NameFrom)\
  188.         pOld->_ref##NameFrom->Replace##NameTo(pOld, this);
  189.  
  190. #define REMOVE_AVLTREE_ACTIVE(ClassFrom, NameFrom, ClassTo, NameTo) \
  191.     while (_top##NameTo)\
  192.     {\
  193.         (void)new UndoSubChange(_top##NameTo);\
  194.         Remove##NameTo(_top##NameTo);\
  195.     }
  196.  
  197. #define SAVE_AVLTREE_PASSIVE(ClassFrom, NameFrom, ClassTo, NameTo) \
  198.     p##ClassTo->_ref##NameFrom = _ref##NameFrom;
  199.  
  200. #define RESTORE_AVLTREE_PASSIVE(ClassFrom, NameFrom, ClassTo, NameTo) \
  201.     {\
  202.         ClassFrom* p##ClassFrom = p##ClassTo->_ref##NameFrom;\
  203.         _ref##NameFrom = 0;\
  204.         _bal##NameFrom = 0;\
  205.         p##ClassFrom->Add##NameTo(this);\
  206.     }\
  207.  
  208. #define REMOVE_AVLTREE_PASSIVE(ClassFrom, NameFrom, ClassTo, NameTo) \
  209.     if (_ref##NameFrom)\
  210.     {\
  211.         ClassFrom* p##ClassFrom = _ref##NameFrom;\
  212.         _ref##NameFrom->Remove##NameTo(this);\
  213.         _ref##NameFrom = p##ClassFrom;\
  214.     }
  215.  
  216. #define CLEANUP_AVLTREE_PASSIVE(ClassFrom, NameFrom, ClassTo, NameTo) \
  217.     _ref##NameFrom = (ClassFrom*)0;\
  218.     _parent##NameFrom = (ClassTo*)0;\
  219.     _left##NameFrom = (ClassTo*)0;\
  220.     _right##NameFrom = (ClassTo*)0;\
  221.     _bal##NameFrom = 0;
  222.  
  223. #define METHODS_AVLTREE_ACTIVE(member, ClassFrom, NameFrom, ClassTo, NameTo) \
  224. void ClassFrom##::Add##NameTo(ClassTo* item)\
  225. {\
  226.     METHOD_AVLTREE_ADD(member, ClassFrom, NameFrom, ClassTo, NameTo) \
  227. }\
  228. \
  229. void ClassFrom##::Remove##NameTo(ClassTo* item)\
  230. {\
  231.     METHOD_AVLTREE_REMOVE(ClassFrom, NameFrom, ClassTo, NameTo) \
  232. }\
  233. \
  234. void ClassFrom##::RemoveAll##NameTo()\
  235. {\
  236.     METHOD_AVLTREE_REMOVEALL(ClassFrom, NameFrom, ClassTo, NameTo) \
  237. }\
  238. \
  239. void ClassFrom##::DeleteAll##NameTo()\
  240. {\
  241.     METHOD_AVLTREE_DELETEALL(ClassFrom, NameFrom, ClassTo, NameTo) \
  242. }\
  243. \
  244. void ClassFrom##::Replace##NameTo(ClassTo* item, ClassTo* newItem)\
  245. {\
  246.     METHOD_AVLTREE_REPLACE(member, ClassFrom, NameFrom, ClassTo, NameTo) \
  247. }\
  248. \
  249. ClassTo* ClassFrom##::GetFirst##NameTo() const\
  250. {\
  251.     METHOD_AVLTREE_GETFIRST(ClassFrom, NameFrom, ClassTo, NameTo) \
  252. }\
  253. \
  254. ClassTo* ClassFrom##::GetLast##NameTo() const\
  255. {\
  256.     METHOD_AVLTREE_GETLAST(ClassFrom, NameFrom, ClassTo, NameTo) \
  257. }\
  258. \
  259. ClassTo* ClassFrom##::GetNext##NameTo(ClassTo* pos) const\
  260. {\
  261.     METHOD_AVLTREE_GETNEXT(ClassFrom, NameFrom, ClassTo, NameTo) \
  262. }\
  263. \
  264. ClassTo* ClassFrom##::GetPrev##NameTo(ClassTo* pos) const\
  265. {\
  266.     METHOD_AVLTREE_GETPREV(ClassFrom, NameFrom, ClassTo, NameTo) \
  267. }\
  268. \
  269. int ClassFrom##::Get##NameTo##Count() const\
  270. {\
  271.     METHOD_AVLTREE_GETCOUNT(ClassFrom, NameFrom, ClassTo, NameTo) \
  272. }
  273.  
  274. #define METHOD_AVLTREE_ADD(member, ClassFrom, NameFrom, ClassTo, NameTo) \
  275.     assert(this);\
  276. \
  277.     assert(item);\
  278.     assert(item->_ref##NameFrom == (ClassFrom*)0);\
  279. \
  280.     _count##NameTo++;\
  281. \
  282.     item->_ref##NameFrom = this;\
  283. \
  284.     if (_top##NameTo)\
  285.     {\
  286.         ClassTo* current = _top##NameTo;\
  287.         while (1)\
  288.         {\
  289.             if (item->member < current->member)\
  290.             {\
  291.                 if (current->_left##NameFrom)\
  292.                 {\
  293.                     current = current->_left##NameFrom;\
  294.                 }\
  295.                 else\
  296.                 {\
  297.                     current->_left##NameFrom = item;\
  298.                     item->_parent##NameFrom = current;\
  299.                     current->_bal##NameFrom--;\
  300.                     break;\
  301.                 }\
  302.             }\
  303.             else\
  304.             {\
  305.                 if (current->_right##NameFrom)\
  306.                 {\
  307.                     current = current->_right##NameFrom;\
  308.                 }\
  309.                 else\
  310.                 {\
  311.                     current->_right##NameFrom = item;\
  312.                     item->_parent##NameFrom = current;\
  313.                     current->_bal##NameFrom++;\
  314.                     break;\
  315.                 }\
  316.             }\
  317.         }\
  318. \
  319.         ClassTo* parent;\
  320.         while (current && current->_bal##NameFrom)\
  321.         {\
  322.             parent = current->_parent##NameFrom;\
  323.             if (parent)\
  324.             {\
  325.                 if (parent->_left##NameFrom == current)\
  326.                 {\
  327.                     parent->_bal##NameFrom--;\
  328.                 }\
  329.                 else\
  330.                 {\
  331.                     parent->_bal##NameFrom++;\
  332.                 }\
  333. \
  334.                 if (parent->_bal##NameFrom == 2)\
  335.                 {\
  336.                     if (current->_bal##NameFrom == -1)\
  337.                     {\
  338.                         ClassTo* sub = current->_left##NameFrom;\
  339.                         parent->_right##NameFrom = sub->_left##NameFrom;\
  340.                         if (sub->_left##NameFrom)\
  341.                         {\
  342.                             sub->_left##NameFrom->_parent##NameFrom = parent;\
  343.                         }\
  344.                         current->_left##NameFrom = sub->_right##NameFrom;\
  345.                         if (sub->_right##NameFrom)\
  346.                         {\
  347.                             sub->_right##NameFrom->_parent##NameFrom = current;\
  348.                         }\
  349.                         sub->_parent##NameFrom = parent->_parent##NameFrom;\
  350.                         sub->_left##NameFrom = parent;\
  351.                         parent->_parent##NameFrom = sub;\
  352.                         sub->_right##NameFrom = current;\
  353.                         current->_parent##NameFrom = sub;\
  354.                         if (sub->_parent##NameFrom)\
  355.                         {\
  356.                             if (sub->_parent##NameFrom->_left##NameFrom == parent)\
  357.                             {\
  358.                                 sub->_parent##NameFrom->_left##NameFrom = sub;\
  359.                             }\
  360.                             else\
  361.                             {\
  362.                                 sub->_parent##NameFrom->_right##NameFrom = sub;\
  363.                             }\
  364.                         }\
  365.                         else\
  366.                         {\
  367.                             _top##NameTo = sub;\
  368.                         }\
  369.                         parent->_bal##NameFrom = (sub->_bal##NameFrom == 1? -1: 0);\
  370.                         current->_bal##NameFrom = (sub->_bal##NameFrom == -1? 1: 0);\
  371.                         sub->_bal##NameFrom = 0;\
  372.                         current = sub;\
  373.                     }\
  374.                     else\
  375.                     {\
  376.                         parent->_right##NameFrom = current->_left##NameFrom;\
  377.                         if (current->_left##NameFrom)\
  378.                         {\
  379.                             current->_left##NameFrom->_parent##NameFrom = parent;\
  380.                         }\
  381.                         current->_left##NameFrom = parent;\
  382.                         current->_parent##NameFrom = parent->_parent##NameFrom;\
  383.                         parent->_parent##NameFrom = current;\
  384.                         if (current->_parent##NameFrom)\
  385.                         {\
  386.                             if (current->_parent##NameFrom->_left##NameFrom == parent)\
  387.                             {\
  388.                                 current->_parent##NameFrom->_left##NameFrom = current;\
  389.                             }\
  390.                             else\
  391.                             {\
  392.                                 current->_parent##NameFrom->_right##NameFrom = current;\
  393.                             }\
  394.                         }\
  395.                         else\
  396.                         {\
  397.                             _top##NameTo = current;\
  398.                         }\
  399.                         parent->_bal##NameFrom = 0;\
  400.                         current->_bal##NameFrom = 0;\
  401.                     }\
  402.                 }\
  403.                 else if (parent->_bal##NameFrom == -2)\
  404.                 {\
  405.                     if (current->_bal##NameFrom == 1)\
  406.                     {\
  407.                         ClassTo* sub = current->_right##NameFrom;\
  408.                         parent->_left##NameFrom = sub->_right##NameFrom;\
  409.                         if (sub->_right##NameFrom)\
  410.                         {\
  411.                             sub->_right##NameFrom->_parent##NameFrom = parent;\
  412.                         }\
  413.                         current->_right##NameFrom = sub->_left##NameFrom;\
  414.                         if (sub->_left##NameFrom)\
  415.                         {\
  416.                             sub->_left##NameFrom->_parent##NameFrom = current;\
  417.                         }\
  418.                         sub->_parent##NameFrom = parent->_parent##NameFrom;\
  419.                         sub->_right##NameFrom = parent;\
  420.                         parent->_parent##NameFrom = sub;\
  421.                         sub->_left##NameFrom = current;\
  422.                         current->_parent##NameFrom = sub;\
  423.                         if (sub->_parent##NameFrom)\
  424.                         {\
  425.                             if (sub->_parent##NameFrom->_right##NameFrom == parent)\
  426.                             {\
  427.                                 sub->_parent##NameFrom->_right##NameFrom = sub;\
  428.                             }\
  429.                             else\
  430.                             {\
  431.                                 sub->_parent##NameFrom->_left##NameFrom = sub;\
  432.                             }\
  433.                         }\
  434.                         else\
  435.                         {\
  436.                             _top##NameTo = sub;\
  437.                         }\
  438.                         parent->_bal##NameFrom = (sub->_bal##NameFrom == -1? 1: 0);\
  439.                         current->_bal##NameFrom = (sub->_bal##NameFrom == 1? -1: 0);\
  440.                         sub->_bal##NameFrom = 0;\
  441.                         current = sub;\
  442.                     }\
  443.                     else\
  444.                     {\
  445.                         parent->_left##NameFrom = current->_right##NameFrom;\
  446.                         if (current->_right##NameFrom)\
  447.                         {\
  448.                             current->_right##NameFrom->_parent##NameFrom = parent;\
  449.                         }\
  450.                         current->_right##NameFrom = parent;\
  451.                         current->_parent##NameFrom = parent->_parent##NameFrom;\
  452.                         parent->_parent##NameFrom = current;\
  453.                         if (current->_parent##NameFrom)\
  454.                         {\
  455.                             if (current->_parent##NameFrom->_right##NameFrom == parent)\
  456.                             {\
  457.                                 current->_parent##NameFrom->_right##NameFrom = current;\
  458.                             }\
  459.                             else\
  460.                             {\
  461.                                 current->_parent##NameFrom->_left##NameFrom = current;\
  462.                             }\
  463.                         }\
  464.                         else\
  465.                         {\
  466.                             _top##NameTo = current;\
  467.                         }\
  468.                         parent->_bal##NameFrom = 0;\
  469.                         current->_bal##NameFrom = 0;\
  470.                     }\
  471.                 }\
  472.                 else\
  473.                 {\
  474.                     current = parent;\
  475.                 }\
  476.             }\
  477.             else\
  478.             {\
  479.                 current = parent;\
  480.             }\
  481.         }\
  482.     }\
  483.     else\
  484.     {\
  485.         _top##NameTo = item;\
  486.     }
  487.  
  488. #define METHOD_AVLTREE_REMOVE(ClassFrom, NameFrom, ClassTo, NameTo) \
  489.     assert(this);\
  490. \
  491.     assert(item);\
  492.     assert(item->_ref##NameFrom == this);\
  493. \
  494.     ClassFrom##::##NameTo##Iterator::Check(item);\
  495. \
  496.     _count##NameTo--;\
  497. \
  498.     ClassTo* subParent = item->_parent##NameFrom;\
  499.     ClassTo* sub = item;\
  500.     /*     item               -                                   */\
  501.     /*      ^        ==>                                          */\
  502.     /*     - -                                                    */\
  503.     if (!item->_left##NameFrom && !item->_right##NameFrom)\
  504.     {\
  505.         if (subParent)\
  506.         {\
  507.             if (subParent->_left##NameFrom == item)\
  508.             {\
  509.                 subParent->_left##NameFrom = 0;\
  510.                 subParent->_bal##NameFrom++;\
  511.             }\
  512.             else\
  513.             {\
  514.                 subParent->_right##NameFrom = 0;\
  515.                 subParent->_bal##NameFrom--;\
  516.             }\
  517.         }\
  518.         else\
  519.         {\
  520.             _top##NameTo = 0;\
  521.         }\
  522.     }\
  523.     else\
  524.     {\
  525.         if (item->_bal##NameFrom > 0)\
  526.         {\
  527.             sub = item->_right##NameFrom;\
  528.             while (sub->_left##NameFrom)\
  529.             {\
  530.                 sub = sub->_left##NameFrom;\
  531.             }\
  532.             subParent = sub->_parent##NameFrom;\
  533.             if (subParent != item)\
  534.             {\
  535.                 subParent->_left##NameFrom = sub->_right##NameFrom;\
  536.                 if (subParent->_left##NameFrom)\
  537.                 {\
  538.                     subParent->_left##NameFrom->_parent##NameFrom = subParent;\
  539.                 }\
  540.                 subParent->_bal##NameFrom++;\
  541.             }\
  542.             else\
  543.             {\
  544.                 item->_bal##NameFrom--;\
  545.             }\
  546.         }\
  547.         else\
  548.         {\
  549.             sub = item->_left##NameFrom;\
  550.             while (sub->_right##NameFrom)\
  551.             {\
  552.                 sub = sub->_right##NameFrom;\
  553.             }\
  554.             subParent = sub->_parent##NameFrom;\
  555.             if (subParent != item)\
  556.             {\
  557.                 subParent->_right##NameFrom = sub->_left##NameFrom;\
  558.                 if (subParent->_right##NameFrom)\
  559.                 {\
  560.                     subParent->_right##NameFrom->_parent##NameFrom = subParent;\
  561.                 }\
  562.                 subParent->_bal##NameFrom--;\
  563.             }\
  564.             else\
  565.             {\
  566.                 item->_bal##NameFrom++;\
  567.             }\
  568.         }\
  569.         sub->_parent##NameFrom = item->_parent##NameFrom;\
  570.         if (item->_parent##NameFrom)\
  571.         {\
  572.             if (item->_parent##NameFrom->_left##NameFrom == item)\
  573.             {\
  574.                 item->_parent##NameFrom->_left##NameFrom = sub;\
  575.             }\
  576.             else\
  577.             {\
  578.                 item->_parent##NameFrom->_right##NameFrom = sub;\
  579.             }\
  580.         }\
  581.         else\
  582.         {\
  583.             _top##NameTo = sub;\
  584.         }\
  585.         if (item->_left##NameFrom != sub)\
  586.         {\
  587.             sub->_left##NameFrom = item->_left##NameFrom;\
  588.             if (item->_left##NameFrom)\
  589.             {\
  590.                 item->_left##NameFrom->_parent##NameFrom = sub;\
  591.             }\
  592.         }\
  593.         if (item->_right##NameFrom != sub)\
  594.         {\
  595.             sub->_right##NameFrom = item->_right##NameFrom;\
  596.             if (item->_right##NameFrom)\
  597.             {\
  598.                 item->_right##NameFrom->_parent##NameFrom = sub;\
  599.             }\
  600.         }\
  601.         sub->_bal##NameFrom = item->_bal##NameFrom;\
  602. \
  603.         if (subParent == item)\
  604.         {\
  605.             subParent = sub;\
  606.         }\
  607.     }\
  608. \
  609.     item->_ref##NameFrom = (ClassFrom*)0;\
  610.     item->_parent##NameFrom = (ClassTo*)0;\
  611.     item->_left##NameFrom = (ClassTo*)0;\
  612.     item->_right##NameFrom = (ClassTo*)0;\
  613.     item->_bal##NameFrom = 0;\
  614. \
  615.     ClassTo* parent = subParent;\
  616.     while (parent && parent->_bal##NameFrom != -1 && parent->_bal##NameFrom != 1)\
  617.     {\
  618.         if (parent->_bal##NameFrom == 2)\
  619.         {\
  620.             ClassTo* current = parent->_right##NameFrom;\
  621.             if (current->_bal##NameFrom == -1)\
  622.             {\
  623.                 ClassTo* sub = current->_left##NameFrom;\
  624.                 parent->_right##NameFrom = sub->_left##NameFrom;\
  625.                 if (sub->_left##NameFrom)\
  626.                 {\
  627.                     sub->_left##NameFrom->_parent##NameFrom = parent;\
  628.                 }\
  629.                 current->_left##NameFrom = sub->_right##NameFrom;\
  630.                 if (sub->_right##NameFrom)\
  631.                 {\
  632.                     sub->_right##NameFrom->_parent##NameFrom = current;\
  633.                 }\
  634.                 sub->_parent##NameFrom = parent->_parent##NameFrom;\
  635.                 sub->_left##NameFrom = parent;\
  636.                 parent->_parent##NameFrom = sub;\
  637.                 sub->_right##NameFrom = current;\
  638.                 current->_parent##NameFrom = sub;\
  639.                 if (sub->_parent##NameFrom)\
  640.                 {\
  641.                     if (sub->_parent##NameFrom->_left##NameFrom == parent)\
  642.                     {\
  643.                         sub->_parent##NameFrom->_left##NameFrom = sub;\
  644.                     }\
  645.                     else\
  646.                     {\
  647.                         sub->_parent##NameFrom->_right##NameFrom = sub;\
  648.                     }\
  649.                 }\
  650.                 else\
  651.                 {\
  652.                     _top##NameTo = sub;\
  653.                 }\
  654.                 parent->_bal##NameFrom = (sub->_bal##NameFrom == 1? -1: 0);\
  655.                 current->_bal##NameFrom = (sub->_bal##NameFrom == -1? 1: 0);\
  656.                 sub->_bal##NameFrom = 0;\
  657.                 parent = sub;\
  658.             }\
  659.             else if (current->_bal##NameFrom == 1)\
  660.             {\
  661.                 parent->_right##NameFrom = current->_left##NameFrom;\
  662.                 if (current->_left##NameFrom)\
  663.                 {\
  664.                     current->_left##NameFrom->_parent##NameFrom = parent;\
  665.                 }\
  666.                 current->_left##NameFrom = parent;\
  667.                 current->_parent##NameFrom = parent->_parent##NameFrom;\
  668.                 parent->_parent##NameFrom = current;\
  669.                 if (current->_parent##NameFrom)\
  670.                 {\
  671.                     if (current->_parent##NameFrom->_left##NameFrom == parent)\
  672.                     {\
  673.                         current->_parent##NameFrom->_left##NameFrom = current;\
  674.                     }\
  675.                     else\
  676.                     {\
  677.                         current->_parent##NameFrom->_right##NameFrom = current;\
  678.                     }\
  679.                 }\
  680.                 else\
  681.                 {\
  682.                     _top##NameTo = current;\
  683.                 }\
  684.                 parent->_bal##NameFrom = 0;\
  685.                 current->_bal##NameFrom = 0;\
  686.                 parent = current;\
  687.             }\
  688.             else\
  689.             {\
  690.                 parent->_right##NameFrom = current->_left##NameFrom;\
  691.                 if (current->_left##NameFrom)\
  692.                 {\
  693.                     current->_left##NameFrom->_parent##NameFrom = parent;\
  694.                 }\
  695.                 current->_left##NameFrom = parent;\
  696.                 current->_parent##NameFrom = parent->_parent##NameFrom;\
  697.                 parent->_parent##NameFrom = current;\
  698.                 if (current->_parent##NameFrom)\
  699.                 {\
  700.                     if (current->_parent##NameFrom->_left##NameFrom == parent)\
  701.                     {\
  702.                         current->_parent##NameFrom->_left##NameFrom = current;\
  703.                     }\
  704.                     else\
  705.                     {\
  706.                         current->_parent##NameFrom->_right##NameFrom = current;\
  707.                     }\
  708.                 }\
  709.                 else\
  710.                 {\
  711.                     _top##NameTo = current;\
  712.                 }\
  713.                 parent->_bal##NameFrom = 1;\
  714.                 current->_bal##NameFrom = -1;\
  715.                 break;\
  716.             }\
  717.         }\
  718.         else if (parent->_bal##NameFrom == -2)\
  719.         {\
  720.             ClassTo* current = parent->_left##NameFrom;\
  721.             if (current->_bal##NameFrom == 1)\
  722.             {\
  723.                 ClassTo* sub = current->_right##NameFrom;\
  724.                 parent->_left##NameFrom = sub->_right##NameFrom;\
  725.                 if (sub->_right##NameFrom)\
  726.                 {\
  727.                     sub->_right##NameFrom->_parent##NameFrom = parent;\
  728.                 }\
  729.                 current->_right##NameFrom = sub->_left##NameFrom;\
  730.                 if (sub->_left##NameFrom)\
  731.                 {\
  732.                     sub->_left##NameFrom->_parent##NameFrom = current;\
  733.                 }\
  734.                 sub->_parent##NameFrom = parent->_parent##NameFrom;\
  735.                 sub->_right##NameFrom = parent;\
  736.                 parent->_parent##NameFrom = sub;\
  737.                 sub->_left##NameFrom = current;\
  738.                 current->_parent##NameFrom = sub;\
  739.                 if (sub->_parent##NameFrom)\
  740.                 {\
  741.                     if (sub->_parent##NameFrom->_right##NameFrom == parent)\
  742.                     {\
  743.                         sub->_parent##NameFrom->_right##NameFrom = sub;\
  744.                     }\
  745.                     else\
  746.                     {\
  747.                         sub->_parent##NameFrom->_left##NameFrom = sub;\
  748.                     }\
  749.                 }\
  750.                 else\
  751.                 {\
  752.                     _top##NameTo = sub;\
  753.                 }\
  754.                 parent->_bal##NameFrom = (sub->_bal##NameFrom == -1? 1: 0);\
  755.                 current->_bal##NameFrom = (sub->_bal##NameFrom == 1? -1: 0);\
  756.                 sub->_bal##NameFrom = 0;\
  757.                 parent = sub;\
  758.             }\
  759.             else if (current->_bal##NameFrom == -1)\
  760.             {\
  761.                 parent->_left##NameFrom = current->_right##NameFrom;\
  762.                 if (current->_right##NameFrom)\
  763.                 {\
  764.                     current->_right##NameFrom->_parent##NameFrom = parent;\
  765.                 }\
  766.                 current->_right##NameFrom = parent;\
  767.                 current->_parent##NameFrom = parent->_parent##NameFrom;\
  768.                 parent->_parent##NameFrom = current;\
  769.                 if (current->_parent##NameFrom)\
  770.                 {\
  771.                     if (current->_parent##NameFrom->_right##NameFrom == parent)\
  772.                     {\
  773.                         current->_parent##NameFrom->_right##NameFrom = current;\
  774.                     }\
  775.                     else\
  776.                     {\
  777.                         current->_parent##NameFrom->_left##NameFrom = current;\
  778.                     }\
  779.                 }\
  780.                 else\
  781.                 {\
  782.                     _top##NameTo = current;\
  783.                 }\
  784.                 parent->_bal##NameFrom = 0;\
  785.                 current->_bal##NameFrom = 0;\
  786.                 parent = current;\
  787.             }\
  788.             else\
  789.             {\
  790.                 parent->_left##NameFrom = current->_right##NameFrom;\
  791.                 if (current->_right##NameFrom)\
  792.                 {\
  793.                     current->_right##NameFrom->_parent##NameFrom = parent;\
  794.                 }\
  795.                 current->_right##NameFrom = parent;\
  796.                 current->_parent##NameFrom = parent->_parent##NameFrom;\
  797.                 parent->_parent##NameFrom = current;\
  798.                 if (current->_parent##NameFrom)\
  799.                 {\
  800.                     if (current->_parent##NameFrom->_right##NameFrom == parent)\
  801.                     {\
  802.                         current->_parent##NameFrom->_right##NameFrom = current;\
  803.                     }\
  804.                     else\
  805.                     {\
  806.                         current->_parent##NameFrom->_left##NameFrom = current;\
  807.                     }\
  808.                 }\
  809.                 else\
  810.                 {\
  811.                     _top##NameTo = current;\
  812.                 }\
  813.                 parent->_bal##NameFrom = -1;\
  814.                 current->_bal##NameFrom = 1;\
  815.                 break;\
  816.             }\
  817.         }\
  818. \
  819.         if (parent->_parent##NameFrom)\
  820.         {\
  821.             if (parent->_parent##NameFrom->_left##NameFrom == parent)\
  822.             {\
  823.                 parent->_parent##NameFrom->_bal##NameFrom++;\
  824.             }\
  825.             else\
  826.             {\
  827.                 parent->_parent##NameFrom->_bal##NameFrom--;\
  828.             }\
  829.         }\
  830. \
  831.         parent = parent->_parent##NameFrom;\
  832.     }\
  833.  
  834. #define METHOD_AVLTREE_REMOVEALL(ClassFrom, NameFrom, ClassTo, NameTo) \
  835.     assert(this);\
  836. \
  837.     while (_top##NameTo)\
  838.     {\
  839.         Remove##NameTo(_top##NameTo);\
  840.     }
  841.  
  842. #define METHOD_AVLTREE_DELETEALL(ClassFrom, NameFrom, ClassTo, NameTo) \
  843.     assert(this);\
  844. \
  845.     while (_top##NameTo)\
  846.     {\
  847.         delete _top##NameTo;\
  848.     }
  849.  
  850. #define METHOD_AVLTREE_REPLACE(member, ClassFrom, NameFrom, ClassTo, NameTo) \
  851.     assert(this);\
  852. \
  853.     assert(item);\
  854.     assert(item->_ref##NameFrom == this);\
  855. \
  856.     assert(newItem);\
  857.     assert(newItem->_ref##NameFrom == (ClassFrom*)0);\
  858. \
  859.     if (item->member == newItem->member)\
  860.     {\
  861.         ClassFrom##::##NameTo##Iterator::Check(item, newItem);\
  862.         if (_top##NameTo == item)\
  863.         {\
  864.             _top##NameTo = newItem;\
  865.         }\
  866.         if (item->_parent##NameFrom)\
  867.         {\
  868.             if (item->_parent##NameFrom->_left##NameFrom == item)\
  869.             {\
  870.                 item->_parent##NameFrom->_left##NameFrom = newItem;\
  871.             }\
  872.             else if (item->_parent##NameFrom->_right##NameFrom == item)\
  873.             {\
  874.                 item->_parent##NameFrom->_right##NameFrom = newItem;\
  875.             }\
  876.         }\
  877.         newItem->_ref##NameFrom = this;\
  878.         newItem->_parent##NameFrom = item->_parent##NameFrom;\
  879.         newItem->_left##NameFrom = item->_left##NameFrom;\
  880.         newItem->_right##NameFrom = item->_right##NameFrom;\
  881.         newItem->_bal##NameFrom = item->_bal##NameFrom;\
  882.         item->_ref##NameFrom = (ClassFrom*)0;\
  883.         item->_parent##NameFrom = (ClassTo*)0;\
  884.         item->_left##NameFrom = (ClassTo*)0;\
  885.         item->_right##NameFrom = (ClassTo*)0;\
  886.         item->_bal##NameFrom = 0;\
  887.     }\
  888.     else\
  889.     {\
  890.         ClassFrom##::##NameTo##Iterator::Check(item);\
  891.         Remove##NameTo(item);\
  892.         Add##NameTo(newItem);\
  893.     }
  894.  
  895. #define METHOD_AVLTREE_GETFIRST(ClassFrom, NameFrom, ClassTo, NameTo) \
  896.     assert(this);\
  897. \
  898.     ClassTo* result = _top##NameTo;\
  899.     if (result)\
  900.     {\
  901.         while (result->_left##NameFrom)\
  902.         {\
  903.             result = result->_left##NameFrom;\
  904.         }\
  905.     }\
  906. \
  907.     return result;
  908.  
  909. #define METHOD_AVLTREE_GETLAST(ClassFrom, NameFrom, ClassTo, NameTo) \
  910.     assert(this);\
  911. \
  912.     ClassTo* result = _top##NameTo;\
  913.     if (result)\
  914.     {\
  915.         while (result->_right##NameFrom)\
  916.         {\
  917.             result = result->_right##NameFrom;\
  918.         }\
  919.     }\
  920. \
  921.     return result;
  922.  
  923. #define METHOD_AVLTREE_GETNEXT(ClassFrom, NameFrom, ClassTo, NameTo) \
  924.     assert(this);\
  925. \
  926.     ClassTo* result = 0;\
  927.     if (pos == (ClassTo*)0)\
  928.     {\
  929.         result = _top##NameTo;\
  930.         if (result)\
  931.         {\
  932.             while (result->_left##NameFrom)\
  933.             {\
  934.                 result = result->_left##NameFrom;\
  935.             }\
  936.         }\
  937.     }\
  938.     else\
  939.     {\
  940.         assert(pos->_ref##NameFrom == this);\
  941. \
  942.         if (pos->_right##NameFrom)\
  943.         {\
  944.             result = pos->_right##NameFrom;\
  945.             while (result->_left##NameFrom)\
  946.             {\
  947.                 result = result->_left##NameFrom;\
  948.             }\
  949.         }\
  950.         else\
  951.         {\
  952.             result = pos->_parent##NameFrom;\
  953.             while (result && result->_right##NameFrom == pos)\
  954.             {\
  955.                 pos = result;\
  956.                 result = pos->_parent##NameFrom;\
  957.             }\
  958.         }\
  959.     }\
  960. \
  961.     return result;
  962.  
  963. #define METHOD_AVLTREE_GETPREV(ClassFrom, NameFrom, ClassTo, NameTo) \
  964.     assert(this);\
  965. \
  966.     ClassTo* result = 0;\
  967.     if (pos == (ClassTo*)0)\
  968.     {\
  969.         result = _top##NameTo;\
  970.         if (result)\
  971.         {\
  972.             while (result->_right##NameFrom)\
  973.             {\
  974.                 result = result->_right##NameFrom;\
  975.             }\
  976.         }\
  977.     }\
  978.     else\
  979.     {\
  980.         assert(pos->_ref##NameFrom == this);\
  981. \
  982.         if (pos->_left##NameFrom)\
  983.         {\
  984.             result = pos->_left##NameFrom;\
  985.             while (result->_right##NameFrom)\
  986.             {\
  987.                 result = result->_right##NameFrom;\
  988.             }\
  989.         }\
  990.         else\
  991.         {\
  992.             result = pos->_parent##NameFrom;\
  993.             while (result && result->_left##NameFrom == pos)\
  994.             {\
  995.                 pos = result;\
  996.                 result = pos->_parent##NameFrom;\
  997.             }\
  998.         }\
  999.     }\
  1000. \
  1001.     return result;
  1002.  
  1003. #define METHOD_AVLTREE_GETCOUNT(ClassFrom, NameFrom, ClassTo, NameTo) \
  1004.     assert(this);\
  1005.     return _count##NameTo;
  1006.  
  1007. #define METHODS_AVLTREE_PASSIVE(ClassFrom, NameFrom, ClassTo, NameTo)
  1008.  
  1009. #ifndef _BODY_AVLTREE_FIND
  1010. #define _BODY_AVLTREE_FIND(member, value, ClassFrom, NameFrom, ClassTo, NameTo) \
  1011.     ClassTo* result = 0;\
  1012.     if (_top##NameTo)\
  1013.     {\
  1014.         ClassTo* item = _top##NameTo;\
  1015.         while (1)\
  1016.         {\
  1017.             if (item->member == value)\
  1018.             {\
  1019.                 result = item;\
  1020.                 break;\
  1021.             }\
  1022. \
  1023.             if (value <= item->member)\
  1024.             {\
  1025.                 if (item->_left##NameFrom)\
  1026.                 {\
  1027.                     item = item->_left##NameFrom;\
  1028.                 }\
  1029.                 else\
  1030.                 {\
  1031.                     break;\
  1032.                 }\
  1033.             }\
  1034.             else\
  1035.             {\
  1036.                 if (item->_right##NameFrom)\
  1037.                 {\
  1038.                     item = item->_right##NameFrom;\
  1039.                 }\
  1040.                 else\
  1041.                 {\
  1042.                     break;\
  1043.                 }\
  1044.             }\
  1045.         }\
  1046.     }
  1047. #endif
  1048.  
  1049. #define BODY_AVLTREE_FIND(member, value, ClassFrom, NameFrom, ClassTo, NameTo) \
  1050.     _BODY_AVLTREE_FIND(member, value, ClassFrom, NameFrom, ClassTo, NameTo) \
  1051.     if (result)\
  1052.     {\
  1053.         ClassTo* prev##NameTo = GetPrev##NameTo(result);\
  1054.         while (prev##NameTo && prev##NameTo->member == value)\
  1055.         {\
  1056.             result = prev##NameTo;\
  1057.             prev##NameTo = GetPrev##NameTo(result);\
  1058.         }\
  1059.     }\
  1060.     return result;
  1061.  
  1062. #define BODY_AVLTREE_FINDREVERSE(member, value, ClassFrom, NameFrom, ClassTo, NameTo) \
  1063.     _BODY_AVLTREE_FIND(member, value, ClassFrom, NameFrom, ClassTo, NameTo) \
  1064.     if (result)\
  1065.     {\
  1066.         ClassTo* next##NameTo = GetNext##NameTo(result);\
  1067.         while (next##NameTo && next##NameTo->member == value)\
  1068.         {\
  1069.             result = next##NameTo;\
  1070.             next##NameTo = GetNext##NameTo(result);\
  1071.         }\
  1072.     }\
  1073.     return result;
  1074.  
  1075. #define BODY_AVLTREE_FINDEQUALORBIGGER(member, value, ClassFrom, NameFrom, ClassTo, NameTo) \
  1076.     ClassTo* result = 0;\
  1077.     if (_top##NameTo)\
  1078.     {\
  1079.         ClassTo* item = _top##NameTo;\
  1080.         while (1)\
  1081.         {\
  1082.             if (item->member == value)\
  1083.             {\
  1084.                 result = item;\
  1085.                 ClassTo* prev##NameTo = GetPrev##NameTo(result);\
  1086.                 while (prev##NameTo && prev##NameTo->member == value)\
  1087.                 {\
  1088.                     result = prev##NameTo;\
  1089.                     prev##NameTo = GetPrev##NameTo(result);\
  1090.                 }\
  1091.                 break;\
  1092.             }\
  1093. \
  1094.             if (value <= item->member)\
  1095.             {\
  1096.                 if (item->_left##NameFrom)\
  1097.                 {\
  1098.                     item = item->_left##NameFrom;\
  1099.                 }\
  1100.                 else\
  1101.                 {\
  1102.                     result = item;\
  1103.                     break;\
  1104.                 }\
  1105.             }\
  1106.             else\
  1107.             {\
  1108.                 if (item->_right##NameFrom)\
  1109.                 {\
  1110.                     item = item->_right##NameFrom;\
  1111.                 }\
  1112.                 else\
  1113.                 {\
  1114.                     result = GetNext##NameTo(item);\
  1115.                     break;\
  1116.                 }\
  1117.             }\
  1118.         }\
  1119.     }\
  1120. \
  1121.     return result;
  1122.  
  1123.  
  1124. #define BODY_AVLTREE_FINDEQUALORSMALLER(member, value, ClassFrom, NameFrom, ClassTo, NameTo) \
  1125.     ClassTo* result = 0;\
  1126.     if (_top##NameTo)\
  1127.     {\
  1128.         ClassTo* item = _top##NameTo;\
  1129.         while (1)\
  1130.         {\
  1131.             if (item->member == value)\
  1132.             {\
  1133.                 result = item;\
  1134.                 ClassTo* next##NameTo = GetNext##NameTo(result);\
  1135.                 while (next##NameTo && next##NameTo->member == value)\
  1136.                 {\
  1137.                     result = next##NameTo;\
  1138.                     next##NameTo = GetNext##NameTo(result);\
  1139.                 }\
  1140.                 break;\
  1141.             }\
  1142. \
  1143.             if (value <= item->member)\
  1144.             {\
  1145.                 if (item->_left##NameFrom)\
  1146.                 {\
  1147.                     item = item->_left##NameFrom;\
  1148.                 }\
  1149.                 else\
  1150.                 {\
  1151.                     result = GetPrev##NameTo(item);\
  1152.                     break;\
  1153.                 }\
  1154.             }\
  1155.             else\
  1156.             {\
  1157.                 if (item->_right##NameFrom)\
  1158.                 {\
  1159.                     item = item->_right##NameFrom;\
  1160.                 }\
  1161.                 else\
  1162.                 {\
  1163.                     result = item;\
  1164.                     break;\
  1165.                 }\
  1166.             }\
  1167.         }\
  1168.     }\
  1169. \
  1170.     return result;
  1171.  
  1172. #define WRITE_AVLTREE_ACTIVE(ClassFrom, NameFrom, ClassTo, NameTo) \
  1173.     rCArchive << Get##NameTo##Count();\
  1174.     { for (ClassTo* item = GetFirst##NameTo(); item; item = GetNext##NameTo(item))\
  1175.           rCArchive << item->_index; }
  1176.  
  1177. #define READ_AVLTREE_ACTIVE(ClassFrom, NameFrom, ClassTo, NameTo) \
  1178.     {\
  1179.         int count;\
  1180.         int index;\
  1181. \
  1182.         rCArchive >> count;\
  1183.         for (int i = 0; i < count; i++)\
  1184.         {\
  1185.             rCArchive >> index;\
  1186.             Add##NameTo((ClassTo*)(pointerArray[index]));\
  1187.         }\
  1188.     }
  1189.  
  1190. #endif
  1191.